# -*- coding:utf-8 -*-
'''
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路：笨方法首先找到根root然后中序遍历，最后找到pNode位置然后返回下一个节点
        1如果有右子树，则找右子树的最左节点
        2没右子树，则找第一个当前节点是父节点左孩子的节点
        3根节点返回空
'''
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None


class Solution:
    def GetNext(self, pNode):
        if not pNode: return
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        while pNode.next:
            if pNode.next.left == pNode:
                return pNode.next
            pNode = pNode.next
        return
    # def GetNext(self, pNode):
    #     # write code here
    #     cur = pNode
    #     while cur.next:
    #         cur = cur.next
    #     self.stack = []
    #     self.midOrder(cur)
    #     index = self.stack.index(pNode)
    #     return self.stack[index + 1] if index < len(self.stack) - 1 else None
    #
    # def midOrder(self, root):
    #     if not root: return
    #     self.midOrder(root.left)
    #     self.stack.append(root)
    #     self.midOrder(root.right)